1
Definizione del Problema Convesso in Forma Standard
MATH008Lesson 4
00:00

Un problema di ottimizzazione convessa in forma standard è la base della programmazione matematica moderna. È definito da una funzione obiettivo convessa $f_0$, vincoli di disuguaglianza convessi $f_i$ e affini vincoli di uguaglianza. Definendo il problema sull'intersezione di questi domini $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, garantiamo che ogni ottimo locale sia anche un ottimo globale.

1. Anatomia Matematica della Forma Standard

Il problema è formalmente enunciato come:

$$\begin{aligned} &\text{minimizza} && f_0(x) \\ &\text{soggetto a} && f_i(x) \leq 0, \quad i = 1, \dots, m \\ &&& a_i^T x = b_i, \quad i = 1, \dots, p \end{aligned}$$

L'insieme ammissibile è definito come $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. Un requisito fondamentale per la convessità è che i vincoli di uguaglianza debbano essere affini ($Ax = b$), poiché le uguaglianze non lineari generano generalmente insiemi non convessi.

2. L'Interpretazione Geometrica dell'Epigrafico

Il problema in forma epigrafica ci permette di interpretare l'ottimizzazione in modo geometrico nello 'spazio grafico' $(x, t)$. Introducendo una variabile ausiliaria $t$, minimizziamo $t$ soggetta al vincolo $(x, t) \in \text{epi } f_0$. Ciò dimostra che l'insieme ammissibile, qualsiasi insieme di livello inferiore e l'insieme ottimale sono intrinsecamente convessi.

3. Il Pericolo dell'Implicito vs. Esplicito

Un malinteso comune è che spostare i vincoli nell'obiettivo (rendendoli impliciti) semplifichi il problema. Tuttavia, rendere i vincoli impliciti non ha reso il problema più facile da analizzare o risolvere, anche se il problema risultante è nominalmente non vincolato. Ciò è particolarmente vero nel modello modello Oracle (scatola nera), dove valutiamo $f(x)$ e le sue derivate a un costo senza conoscere la struttura esplicita.

4. Applicazioni nel Mondo Reale

  • Teoria del Portafoglio: Minimizzazione del rischio $\text{var}(c^T x) = x^T \Sigma x$ per 4 asset (es. Asset 1 con rendimento 12%/SD 20%).
  • Ingegneria: Vincoli strutturali come $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
  • Probabilità: Vincoli sul rischio di perdita $\Phi^{-1}(\beta) \leq 0$.
🎯 Principio Fondamentale
La condizione di ottimalità per una funzione $f_0$ differenziabile è data da $\nabla f_0(x)^T(y - x) \geq 0$ per ogni $y$ ammissibile. Ciò implica che il gradiente deve essere un iperpiano di supporto all'insieme ammissibile nel punto ottimo.